package 区间;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * 这个要 真实区间 不是简单计数了 -> 难度增加
 */
public class 合并区间56 {
    public List<int[]> merge(int[][] intervals) {
        // 头同/不同 都 升序！
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            list.add(new int[]{intervals[i][0], intervals[i][1]});
        }
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if(a[0] != b[0]){
                    return a[0]-b[0];
                }else {
                    return a[1]-b[1]; // 这是1 不是0
                }
            }
        });

        // 若消去while 需要初始化 l r
        int l = list.get(0)[0], r = list.get(0)[1]; // 新的[0]
        List<int[]> resList = new ArrayList<>(); // 要用新的list, 要不就误删 题干list的末尾了
        resList.add(new int[]{l,r});
        List<int[]> kongdangList = new ArrayList<>();
        //合并
        for (int i = 1; i < list.size(); i++) {
            int thisR = list.get(i)[1];
            int thisL = list.get(i)[0];
            // 删 覆盖 ( 14 23 )
            if(r >= thisR){
                continue;
            }
            // 相交
            else if(r >= thisL){
                r = thisR;
                resList.remove(resList.size()-1);
                resList.add(new int[]{l,r});
            }
            // 相离
            else if(r < thisL){
                l = thisL;
                r = thisR;
                resList.add(new int[]{l,r});
                kongdangList.add(new int[]{resList.get(resList.size()-2)[1],list.get(i)[0]});
            }
        }

//        // list -> [][]
//        int n = resList.size();
//        int[][] res =new int[n][2];
//        for (int i = 0; i < resList.size(); i++) {
//            int L = resList.get(i)[0];
//            int R = resList.get(i)[1];
//            res[i][0] = L;
//            res[i][1] = R;
//        }
        return kongdangList;
    }

    @Test
    public void test() {
        int[][] p = {{1,3},{2,6},{7,8},{9,10}};
//        int[][] p = {{1,4},{0,4}};
//        int[][] res = merge(p);
//        System.out.println(1);
        List<int[]> kongdangList = merge(p);
        for (int[] ints : kongdangList) {
            System.out.println(ints[0]+","+ints[1]);
        }
        System.out.println();
    }

}
